﻿using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ArrayCode.Slidingwindow
{
    //滑动窗口解法
    //不断调节子序列的起始位置和终止位置，从而得出我们想要的结果
    //主要确定三点：
    //1)窗口内是什么
    //2)如何移动窗口的起始位置
    //3)如何移动窗口的结束位置
    class Slidingwindow
    {
        //========================================= 力扣209 长度最小的子数组
        //给定一个含有n个正整数的数组和一个正整数target。
        //找出改数组中满足其和 >= target 的长度最小的连续子数组[numsl, numsl+1, ..., numsr-1, numsr],并返回其长度
        //如果不存在符合条件的子数组返回0.
        public int MinSubArrayLen(int target, int[] nums)
        {
            //时间复杂度：O(n)  每个元素被操作两次，所以时间复杂度是2*n
            //空间复杂度：O(1)  
            int i = 0;//滑动窗口起始位置
            int sum = 0;//滑动窗口数值之和
            int len = 0;//滑动窗口长度
            for(int j = 0;j < nums.Length;j++)
            {
                sum += nums[j];
                while(sum >= target)//使用while，每次更新i(起始位置），并不断比较子序列是否符合条件
                {
                    int curlen = j - i + 1;//取子序列长度
                    if (len == 0)
                        len = curlen;
                    else
                        len = curlen < len ? curlen : len;
                    sum -= nums[i++];//滑动窗口的精髓之处，不断变更i(子序列的起始位置)
                }
            }
            return len;
        }


        //====================================== 力扣904 水果成篮
        //从一排树中，第i颗数产生tree[i]型的水果
        //你可以从你选择的任何树开始，然后重复执行以下步骤
        //1.把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
        //2.移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
        //请注意，在选择一棵树之后，你没有任何选择：你必须执行步骤1，然后执行步骤2，然后返回步骤1，然后执行步骤2，以此类推，直至停止
        //你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果
        //你能收集的水果树的最大总量是多少
        public int TotalFruit(int[] tree)
        {
            int ans = 0, i = 0;//i是最小的小标满足[i,j]是合法的子序列
            Hashtable count = new Hashtable();//徐磊中各种类型的数量，使得我们可以很快知道子序列中是否含有3种类型
            for(int j = 0;j<tree.Length;++j)
            {
                AddHash(count, tree[i], 1);
                while(count.Count >= 3)
                {
                    AddHash(count, tree[i], -1);
                    if(!count.ContainsKey(tree[i]) || (int)count[tree[i]] == 0)
                    {
                        count.Remove(tree[i]);
                    }
                    i++;
                }
            }
            return ans;
        }
        private void AddHash(Hashtable hashtable, int key, int Addvalue)
        {
            if(hashtable.ContainsKey(key))
            {
                int cur = (int)hashtable[key];
                Addvalue += cur;
                hashtable.Remove(key);
            }
            hashtable.Add(key, Addvalue);
        }

        //======================================== 力扣76 最小覆盖子串
        //给定一个字符串s，一个字符串t。返回s中涵盖t所有字符的最小字串。
        //如果s中不存在涵盖t所有字符的字串，则返回空字符串"".
        //注意：对于t中重复字符，我们寻找的字符串中该字符数量必须不少于t中该字符数量
        //如果s中存在这样的子串，我们保证它是唯一的答案。

        //private Hashtable ori, cnt;
        //public string MinWindow(string s, string t)
        //{
        //    foreach(char c in t)
        //    {
        //        ++ori[c];
        //    }
        //}
        //private bool Check()
        //{
        //    foreach()
        //    {
        //        if(cnt[])
        //    }
        //}
    }
}
